import random

MIN_MASK_LEN = 0
MAX_MASK_LEN = 5*9


def to_ip_str(ip, mask):
    seg = []
    seg2 = []
    for _ in range(5):
        k = ip % 512
        seg.insert(0, str(k))
        seg2.insert(0, '{0:09b}'.format(k))
        ip = ip >> 9
    ip_str2 = '.'.join(seg2)
    ip_str3 = '.'.join(seg) + '\t(' + ip_str2 + ')' + '/' + str(mask)
    # print(ip_str3)
    ip_str = '.'.join(seg) + '/' + str(mask)
    return ip_str


def gen():
    result = random.randint(0, 3)
    # No overlap
    if result < 2:
        mask1 = random.randint(1, MAX_MASK_LEN)
        prefix1 = random.randint(0, 2**mask1-1)
        prefix2 = random.randint(0, 2**mask1-1)
        while prefix2 == prefix1:
            prefix2 = random.randint(0, 2**mask1-1)
        mask2 = random.randint(mask1, MAX_MASK_LEN)
        length = MAX_MASK_LEN - mask1
        suffix1 = random.randint(0, 2**length-1)
        suffix2 = random.randint(0, 2**length-1)
        ip1 = (prefix1 << length) + suffix1
        ip2 = (prefix2 << length) + suffix2
        ip_str1 = to_ip_str(ip1, mask1)
        ip_str2 = to_ip_str(ip2, mask2)
        if result == 1:
            return ip_str1, ip_str2, False
        else:
            return ip_str2, ip_str1, False
    # Overlap
    else:
        mask1 = random.randint(1, MAX_MASK_LEN)
        mask2 = random.randint(mask1, MAX_MASK_LEN)
        prefix1 = random.randint(0, 2**mask1-1)
        prefix2 = prefix1

        length = MAX_MASK_LEN - mask1
        suffix1 = random.randint(0, 2**length-1)
        suffix2 = random.randint(0, 2**length-1)
        ip1 = (prefix1 << length) + suffix1
        ip2 = (prefix2 << length) + suffix2
        ip_str1 = to_ip_str(ip1, mask1)
        ip_str2 = to_ip_str(ip2, mask2)
        if result == 2:
            return ip_str1, ip_str2, True
        else:
            return ip_str2, ip_str1, True


def answer(ip1, ip2):
    def ip_to_number(ip: str):
        ss = ip.split('/')
        mask = int(ss[1])
        sss = [int(ns) for ns in ss[0].split('.')]
        ip = (sss[0]<<36) + (sss[1]<<27) + (sss[2]<<18) + (sss[3]<<9) + sss[4]
        return ip, mask

    ip_number1, mask1 = ip_to_number(ip1)
    ip_number2, mask2 = ip_to_number(ip2)
    mask = min(mask1, mask2)
    if mask == 0:
        return True
    ip_number1 = ip_number1 & ((2**45-1) << (45-mask))
    ip_number2 = ip_number2 & ((2**45-1) << (45-mask))
    if ip_number2 == ip_number1:
        return True
    return False

TEST = False
if TEST:
    case_list = []
    for _ in range(10):
        ip1, ip2, result = gen()
        r = answer(ip1, ip2)
        print("Testing...\nInput:", ip1, ip2, "\nExpected:", result, "\nGot:", r)

else:
    from Solution import Solution
    s = Solution()
    for _ in range(20):
        ip1, ip2, result = gen()
        r = s.answer(ip1, ip2)
        if r != result:
            print("Test Failed\nInput:", ip1, ip2, "\nExpected:", result, "\nGot:", r)
            exit(1)

    exit(0)